package code1_100.code60_70;

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 *
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 */
public class _61rotateRight {

    /**
     *
     * 模拟
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.1 MB     * , 在所有 Java 提交中击败了     * 5.40%     * 的用户
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight0(ListNode head, int k) {
        if(head==null||head.next==null)return head;
        // 获取数组长度
        int length = 0;
        ListNode node = head;
        while (node!=null){
            ++length;
            node = node.next;
        }
        // 获取旋转次数
        k = k%length;
        if(k==0)return head;
        // 更新到第K个节点
        ListNode origin = head;
        for (int i = 0; i < length-k-1; i++) {
            origin = origin.next;
        }
        ListNode right = origin.next;
        origin.next = null;

        node = right;
        while (node!=null){
            if(node.next == null){
                node.next = head;
                break;
            }else {
                node = node.next;
            }
        }
        return right;
    }

    /**
     * 题解思路 ： 闭合为环，然后指定位置断开
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38 MB     * , 在所有 Java 提交中击败了     * 6.74%     * 的用户
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null)return head;
        ListNode node = head;
        int length = 0;
        while (node.next!=null){
            node = node.next;
            ++length;
        }
        k = k%(length+1);
        if(k==0)return head;
        // 连接成环
        node.next = head;
        // 断环
        for (int i = 0; i < length - k; i++) {
            head = head.next;
        }
        ListNode res = head.next;
        head.next = null;
        return res;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(0);
        node.next = new ListNode(1);
//        node.next.next = new ListNode(2);
        rotateRight(node,4);
    }
}
